/*
 * Copyright 北京航空航天大学 @ 2015 版权所有
 */
package com.buaa.edu.leetcode.algorithm.array;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * <p>
 * 给定一个数组和一个和，返回其下标等于给定和 
 * Input: numbers={2, 7, 11, 15}, target=9 
 * Output: index1=1, index2=2
 * </p>
 * 
 * @author towan
 * @email tongwenzide@163.com 2015年5月19日
 */
public class TwoSum {
    //数组不一定有序，hash方法
    public int[] twoSum(int[] nums, int target) {
        int []ret = new int[2];
        if(nums==null){
            return ret;
        }
        //建立索引-值的映射 另外还要建立值及出现次数的映射
        Map<Integer,Integer> indexValue = new HashMap<Integer,Integer>();
        Map<Integer,List<Integer>> valueIndex = new HashMap<Integer,List<Integer>>();
        for(int i=0;i<nums.length;i++){
            //索引到值的映射
            indexValue.put(i, nums[i]);
            
            //值到索引的映射,可能存在多个
            if(valueIndex.containsKey(nums[i])){
                valueIndex.get(nums[i]).add(i);
            }else{
                List<Integer> index  = new ArrayList<Integer>();
                index.add(i);
                valueIndex.put(nums[i], index);
            }
        }
        //如果中间的数字存在
        if(target%2==0 && valueIndex.containsKey(target/2) && valueIndex.get(target/2).size()>=2){
            List<Integer> list = valueIndex.get(target/2);
            int a = list.get(0).intValue();
            int b = list.get(1).intValue();
            ret[0] = 1+(a>b?b:a);
            ret[1] = 1+(a<b?b:a);
            return ret;
        }
        for(int i=0;i<nums.length;i++){
            //去除两个相同的情况
            if(valueIndex.containsKey(target-indexValue.get(i)) && target!=2*indexValue.get(i)){
                int a = valueIndex.get(target-indexValue.get(i)).get(0).intValue();
                ret[0] = 1+(i>a?a:i);
                ret[1] = 1+(i<a?a:i);
                return ret;
            }
            
        }
        return ret;
    }
    public static void main(String[] args) {
        int []arr = {3,2,4};
        int target = 6;
        TwoSum twoSum = new TwoSum();
        int[] twoSum2 = twoSum.twoSum(arr, target);
        System.out.println(Arrays.toString(twoSum2));
    }
}
